/* ==========================================
 * JGraphT : a free Java graph-theory library
 * ==========================================
 *
 * Project Info:  http://jgrapht.sourceforge.net/
 * Project Creator:  Barak Naveh (http://sourceforge.net/users/barak_naveh)
 *
 * (C) Copyright 2003-2008, by Barak Naveh and Contributors.
 *
 * This library is free software; you can redistribute it and/or modify it
 * under the terms of the GNU Lesser General Public License as published by
 * the Free Software Foundation; either version 2.1 of the License, or
 * (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
 * License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with this library; if not, write to the Free Software Foundation,
 * Inc.,
 * 59 Temple Place, Suite 330, Boston, MA 02111-1307, USA.
 */
/* -------------------
 * DirectedAcyclicGraph.java
 * -------------------
 * (C) Copyright 2008-2008, by Peter Giles and Contributors.
 *
 * Original Author:  Peter Giles
 * Contributor(s):   John V. Sichi
 *
 * $Id: DirectedAcyclicGraph.java 637 2008-09-28 22:23:11Z perfecthash $
 *
 * Changes
 * -------
 * 17-Mar-2008 : Initial revision (PG);
 * 23-Aug-2008 : Added VisitedBitSetImpl and made it the default (JVS);
 *
 */
package at.tugraz.kmi.css.cbkst2.prereq;

import java.io.Serializable;
import java.util.ArrayList;
import java.util.BitSet;
import java.util.Collections;
import java.util.Comparator;
import java.util.ConcurrentModificationException;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Set;
import java.util.SortedSet;
import java.util.TreeSet;

import javax.annotation.Nonnull;

import edu.uci.ics.jung.graph.DirectedSparseGraph;
import edu.uci.ics.jung.graph.Graph;
import edu.uci.ics.jung.graph.util.EdgeType;
import edu.uci.ics.jung.graph.util.Pair;

/**
 * <p>
 * DirectedAcyclicGraph implements a DAG that can be modified (vertices &amp;
 * edges added and removed), is guaranteed to remain acyclic, and provides fast
 * topological order iteration.
 * </p>
 * 
 * <p>
 * This is done using a dynamic topological sort which is based on the algorithm
 * PK described in "D. Pearce &amp; P. Kelly, 2007: A Dynamic Topological Sort
 * Algorithm for Directed Acyclic Graphs", (see <a
 * href="http://www.mcs.vuw.ac.nz/~djp/files/PK-JEA07.pdf">Paper</a> or <a
 * href="http://doi.acm.org/10.1145/1187436.1210590">ACM link</a> for details).
 * </p>
 * 
 * <p>
 * The implementation differs from the algorithm specified in the above paper in
 * some ways, perhaps most notably in that the topological ordering is stored by
 * default using two HashMaps, which will have some effects on runtime, but also
 * allows for vertex addition and removal, and other operations which are
 * helpful for manipulating or combining DAGs. This storage mechanism is
 * pluggable for subclassers.
 * </p>
 * 
 * <p>
 * This class makes no claims to thread safety, and concurrent usage from
 * multiple threads will produce undefined results.
 * </p>
 * 
 * @author Georg Öttl, georg.oettl@gmail.com
 */
class DirectedAcyclicGraph<V, E> extends DirectedSparseGraph<V, E> {
	// ~ Static fields/initializers
	// ---------------------------------------------

	/**
	 * Exception used in dfsF when a cycle is found
	 * 
	 * @author gilesp
	 */
	public static class CycleFoundException extends Exception {
		private static final long	serialVersionUID	= 5583471522212552754L;
	}

	// ~ Instance fields
	// --------------------------------------------------------

	/**
	 * Region is an *inclusive* range of indices. Esthetically displeasing, but
	 * convenient for our purposes.
	 * 
	 * @author gilesp
	 */
	public static class Region implements Serializable {
		/**
         */
		private static final long	serialVersionUID	= 1L;

		private final int			start;
		private final int			finish;

		public Region(int start, int finish) {
			if (start > finish) {
				throw new IllegalArgumentException(
						"(start > finish): invariant broken");
			}
			this.start = start;
			this.finish = finish;
		}

		public int getSize() {
			return (this.finish - this.start) + 1;
		}

		public boolean isIn(int index) {
			return (index >= this.start) && (index <= this.finish);
		}
	}

	/**
	 * Note, this is a lazy and incomplete implementation, with assumptions that
	 * inputs are in the given topoIndexMap
	 * 
	 * @param <V>
	 * 
	 * @author gilesp
	 */
	private static class TopoComparator<V> implements Comparator<V>,
			Serializable {
		/**
         */
		private static final long			serialVersionUID	= 1L;

		private final TopoOrderMapping<V>	topoOrderMap;

		public TopoComparator(TopoOrderMapping<V> topoOrderMap) {
			this.topoOrderMap = topoOrderMap;
		}

		@Override
		public int compare(V o1, V o2) {
			return this.topoOrderMap.getTopologicalIndex(o1).compareTo(
					this.topoOrderMap.getTopologicalIndex(o2));
		}
	}

	/**
	 * iterator which follows topological order
	 * 
	 * @author gilesp
	 */
	private class TopoIterator implements Iterator<V> {
		private int			currentTopoIndex;
		private final long	updateCountAtCreation;
		private Integer		nextIndex	= null;

		public TopoIterator() {
			this.updateCountAtCreation = DirectedAcyclicGraph.this.topologyUpdateCount;
			this.currentTopoIndex = DirectedAcyclicGraph.this.minTopoIndex - 1;
		}

		private Integer getNextIndex() {
			for (int i = this.currentTopoIndex + 1; i <= DirectedAcyclicGraph.this.maxTopoIndex; i++) {
				if (null != DirectedAcyclicGraph.this.topoOrderMap.getVertex(i)) {
					return i;
				}
			}
			return null;
		}

		@Override
		public boolean hasNext() {
			if (this.updateCountAtCreation != DirectedAcyclicGraph.this.topologyUpdateCount) {
				throw new ConcurrentModificationException();
			}

			this.nextIndex = getNextIndex();
			return this.nextIndex != null;
		}

		@Override
		public V next() {
			if (this.updateCountAtCreation != DirectedAcyclicGraph.this.topologyUpdateCount) {
				throw new ConcurrentModificationException();
			}

			if (this.nextIndex == null) {
				// find nextIndex
				this.nextIndex = getNextIndex();
			}
			if (this.nextIndex == null) {
				throw new NoSuchElementException();
			}
			this.currentTopoIndex = this.nextIndex;
			this.nextIndex = null;
			return DirectedAcyclicGraph.this.topoOrderMap
					.getVertex(this.currentTopoIndex); // topoToVertex.get(currentTopoIndex);
		}

		@Override
		public void remove() {
			if (this.updateCountAtCreation != DirectedAcyclicGraph.this.topologyUpdateCount) {
				throw new ConcurrentModificationException();
			}

			V vertexToRemove = null;
			if (null != (vertexToRemove = DirectedAcyclicGraph.this.topoOrderMap
					.getVertex(this.currentTopoIndex))) {
				DirectedAcyclicGraph.this.topoOrderMap
						.removeVertex(vertexToRemove);
			} else {
				// should only happen if next() hasn't been called
				throw new IllegalStateException();
			}
		}
	}

	/**
	 * For performance tuning, an interface for storing the topological ordering
	 * 
	 * @author gilesp
	 * @param <V>
	 *            The parameter V
	 */
	public interface TopoOrderMapping<V> extends Serializable {
		/**
		 * get the topological index of the given vertex.
		 * 
		 * @param vertex
		 * 
		 * @return the index that the vertex is at, or null if the vertex isn't
		 *         in the topological ordering
		 */
		public Integer getTopologicalIndex(V vertex);

		/**
		 * get the vertex at the given topological index.
		 * 
		 * @param index
		 * 
		 * @return V
		 */
		public V getVertex(Integer index);

		/**
		 * add a vertex at the given topological index.
		 * 
		 * @param index
		 * @param vertex
		 */
		public void putVertex(Integer index, V vertex);

		/**
		 * remove all vertices from the topological ordering
		 */
		public void removeAllVertices();

		/**
		 * remove the given vertex from the topological ordering
		 * 
		 * @param vertex
		 * 
		 * @return the index that the vertex was at, or null if the vertex
		 *         wasn't in the topological ordering
		 */
		public Integer removeVertex(V vertex);
	}

	public interface TopoOrderMappingFactory<V> {
		public TopoOrderMapping<V> getTopoOrderMapping();
	}

	/**
	 * a dual HashMap implementation
	 * 
	 * @author gilesp
	 */
	private class TopoVertexBiMap implements TopoOrderMapping<V>,
			TopoOrderMappingFactory<V> {
		/**
         */
		private static final long		serialVersionUID	= 1L;

		private final Map<Integer, V>	topoToVertex		= new HashMap<Integer, V>();
		private final Map<V, Integer>	vertexToTopo		= new HashMap<V, Integer>();

		@Override
		public Integer getTopologicalIndex(V vertex) {
			return this.vertexToTopo.get(vertex);
		}

		@Override
		public TopoOrderMapping<V> getTopoOrderMapping() {
			return this;
		}

		@Override
		public V getVertex(Integer index) {
			return this.topoToVertex.get(index);
		}

		@Override
		public void putVertex(Integer index, V vertex) {
			this.topoToVertex.put(index, vertex);
			this.vertexToTopo.put(vertex, index);
		}

		@Override
		public void removeAllVertices() {
			this.vertexToTopo.clear();
			this.topoToVertex.clear();
		}

		@Override
		public Integer removeVertex(V vertex) {
			Integer topoIndex = this.vertexToTopo.remove(vertex);
			if (topoIndex != null) {
				this.topoToVertex.remove(topoIndex);
			}
			return topoIndex;
		}
	}

	/**
	 * For performance and flexibility uses an ArrayList for topological index
	 * to vertex mapping, and a HashMap for vertex to topological index mapping.
	 * 
	 * @author gilesp
	 */
	public class TopoVertexMap implements TopoOrderMapping<V>,
			TopoOrderMappingFactory<V> {
		/**
         */
		private static final long		serialVersionUID	= 1L;

		private final List<V>			topoToVertex		= new ArrayList<V>();
		private final Map<V, Integer>	vertexToTopo		= new HashMap<V, Integer>();

		@Override
		public Integer getTopologicalIndex(V vertex) {
			return this.vertexToTopo.get(vertex);
		}

		@Override
		public TopoOrderMapping<V> getTopoOrderMapping() {
			return this;
		}

		@Override
		public V getVertex(Integer index) {
			return this.topoToVertex.get(translateIndex(index));
		}

		@Override
		public void putVertex(Integer index, V vertex) {
			int translatedIndex = translateIndex(index);

			// grow topoToVertex as needed to accommodate elements
			while ((translatedIndex + 1) > this.topoToVertex.size()) {
				this.topoToVertex.add(null);
			}

			this.topoToVertex.set(translatedIndex, vertex);
			this.vertexToTopo.put(vertex, index);
		}

		@Override
		public void removeAllVertices() {
			this.vertexToTopo.clear();
			this.topoToVertex.clear();
		}

		@Override
		public Integer removeVertex(V vertex) {
			Integer topoIndex = this.vertexToTopo.remove(vertex);
			if (topoIndex != null) {
				this.topoToVertex.set(translateIndex(topoIndex), null);
			}
			return topoIndex;
		}

		/**
		 * We translate the topological index to an ArrayList index. We have to
		 * do this because topological indices can be negative, and we want to
		 * do it because we can make better use of space by only needing an
		 * ArrayList of size |AR|.
		 * 
		 * @param unscaledIndex
		 * 
		 * @return the ArrayList index
		 */
		private final int translateIndex(int index) {
			if (index >= 0) {
				return 2 * index;
			}
			return -1 * ((index * 2) - 1);
		}
	}

	// ~ Constructors
	// -----------------------------------------------------------

	/**
	 * this interface allows specification of a strategy for marking vertices as
	 * visited (based on their topological index, so the vertex type isn't part
	 * of the interface).
	 */
	public interface Visited {
		/**
		 * Clear the visited state of the given topological index
		 * 
		 * @param index
		 * 
		 * @throws UnsupportedOperationException
		 *             if the implementation doesn't support (or doesn't need)
		 *             clearance. For example, if the factory vends a new
		 *             instance every time, it is a waste of cycles to clear the
		 *             state after the search of the Affected Region is done, so
		 *             an UnsupportedOperationException *should* be thrown.
		 */
		public void clearVisited(int index)
				throws UnsupportedOperationException;

		/**
		 * has the given topological index been visited?
		 * 
		 * @param index
		 *            the topological index
		 * @return true if visited false otherwise
		 */
		public boolean getVisited(int index);

		/**
		 * mark the given topological index as visited
		 * 
		 * @param index
		 *            the topological index
		 */
		public void setVisited(int index);
	}

	// ~ Methods
	// ----------------------------------------------------------------

	/**
	 * This implementation, somewhat to my surprise, is slower than the
	 * ArrayList version, probably due to its reallocation of the underlying
	 * array for every topology reorder that is required.
	 * 
	 * @author gilesp
	 */
	public static class VisitedArrayImpl implements Visited, VisitedFactory {
		/**
         */
		private static final long	serialVersionUID	= 1L;

		private final boolean[]		visited;

		private final Region		region;

		/**
		 * Constructs empty factory instance
		 */
		public VisitedArrayImpl() {
			this(null);
		}

		public VisitedArrayImpl(Region region) {
			if (region == null) { // make empty instance
				this.visited = null;
				this.region = null;
			} else { // fill in the needed pieces
				this.region = region;

				// initialized to all false by default
				this.visited = new boolean[region.getSize()];
			}
		}

		@Override
		public void clearVisited(int index)
				throws UnsupportedOperationException {
			throw new UnsupportedOperationException();
		}

		@Override
		public Visited getInstance(Region affectedRegion) {
			return new VisitedArrayImpl(affectedRegion);
		}

		@Override
		public boolean getVisited(int index) {
			try {
				return this.visited[index - this.region.start];
			} catch (ArrayIndexOutOfBoundsException e) {
				/*
				 * log.error("Visited set operation out of region boundaries",
				 * e);
				 */
				throw e;
			}
		}

		@Override
		public void setVisited(int index) {
			try {
				this.visited[index - this.region.start] = true;
			} catch (ArrayIndexOutOfBoundsException e) {
				/*
				 * log.error("Visited set operation out of region boundaries",
				 * e);
				 */
				throw e;
			}
		}
	}

	/**
	 * This implementation seems to offer the best performance in most cases. It
	 * grows the internal ArrayList as needed to be as large as |AR|, so it will
	 * be more memory intensive than the HashSet implementation, and unlike the
	 * Array implementation, it will hold on to that memory (it expands, but
	 * never contracts).
	 * 
	 * @author gilesp
	 */
	public static class VisitedArrayListImpl implements Visited, VisitedFactory {
		/**
         */
		private static final long	serialVersionUID	= 1L;

		private final List<Boolean>	visited				= new ArrayList<Boolean>();

		private Region				affectedRegion;

		@Override
		public void clearVisited(int index)
				throws UnsupportedOperationException {
			this.visited.set(translateIndex(index), Boolean.FALSE);
		}

		@Override
		public Visited getInstance(Region affectedRegion) {
			// Make sure visited is big enough
			int minSize = (affectedRegion.finish - affectedRegion.start) + 1;
			/* plus one because the region range is inclusive of both indices */

			while (this.visited.size() < minSize) {
				this.visited.add(Boolean.FALSE);
			}

			this.affectedRegion = affectedRegion;

			return this;
		}

		@Override
		public boolean getVisited(int index) {
			Boolean result = null;

			result = this.visited.get(translateIndex(index));

			return result;
		}

		@Override
		public void setVisited(int index) {
			this.visited.set(translateIndex(index), Boolean.TRUE);
		}

		/**
		 * We translate the topological index to an ArrayList index. We have to
		 * do this because topological indices can be negative, and we want to
		 * do it because we can make better use of space by only needing an
		 * ArrayList of size |AR|.
		 * 
		 * @param unscaledIndex
		 * 
		 * @return the ArrayList index
		 */
		private int translateIndex(int index) {
			return index - this.affectedRegion.start;
		}
	}

	/**
	 * This implementation is close to the performance of VisitedArrayListImpl,
	 * with 1/8 the memory usage.
	 * 
	 * @author perfecthash
	 */
	public static class VisitedBitSetImpl implements Visited, VisitedFactory {
		/**
         */
		private static final long	serialVersionUID	= 1L;

		private final BitSet		visited				= new BitSet();

		private Region				affectedRegion;

		@Override
		public void clearVisited(int index)
				throws UnsupportedOperationException {
			this.visited.clear(translateIndex(index));
		}

		@Override
		public Visited getInstance(Region affectedRegion) {
			this.affectedRegion = affectedRegion;

			return this;
		}

		@Override
		public boolean getVisited(int index) {
			return this.visited.get(translateIndex(index));
		}

		@Override
		public void setVisited(int index) {
			this.visited.set(translateIndex(index), true);
		}

		/**
		 * We translate the topological index to an ArrayList index. We have to
		 * do this because topological indices can be negative, and we want to
		 * do it because we can make better use of space by only needing an
		 * ArrayList of size |AR|.
		 * 
		 * @param unscaledIndex
		 * 
		 * @return the ArrayList index
		 */
		private int translateIndex(int index) {
			return index - this.affectedRegion.start;
		}
	}

	/**
	 * interface for a factory that vends Visited implementations
	 * 
	 * @author gilesp
	 */
	public interface VisitedFactory extends Serializable {
		public Visited getInstance(Region affectedRegion);
	}

	/**
	 * This implementation doesn't seem to perform as well, though I can imagine
	 * circumstances where it should shine (lots and lots of vertices). It also
	 * should have the lowest memory footprint as it only uses storage for
	 * indices that have been visited.
	 * 
	 * @author gilesp
	 */
	public static class VisitedHashSetImpl implements Visited, VisitedFactory {
		/**
         */
		private static final long	serialVersionUID	= 1L;

		private final Set<Integer>	visited				= new HashSet<Integer>();

		@Override
		public void clearVisited(int index)
				throws UnsupportedOperationException {
			throw new UnsupportedOperationException();
		}

		@Override
		public Visited getInstance(Region affectedRegion) {
			this.visited.clear();
			return this;
		}

		@Override
		public boolean getVisited(int index) {
			return this.visited.contains(index);
		}

		@Override
		public void setVisited(int index) {
			this.visited.add(index);
		}
	}

	private static final long					serialVersionUID	= 4522128427004938150L;

	private TopoComparator<V>					topoComparator;

	private TopoOrderMapping<V>					topoOrderMap;

	// ~ Inner Interfaces
	// -------------------------------------------------------

	private int									maxTopoIndex		= 0;

	private int									minTopoIndex		= 0;

	// this update count is used to keep internal topological iterators honest
	private long								topologyUpdateCount	= 0;

	/**
	 * Pluggable VisitedFactory implementation
	 */
	private final VisitedFactory				visitedFactory		= new VisitedBitSetImpl();

	// ~ Inner Classes
	// ----------------------------------------------------------

	/**
	 * Pluggable TopoOrderMappingFactory implementation
	 */
	private final TopoOrderMappingFactory<V>	topoOrderFactory	= new TopoVertexBiMap();

	public DirectedAcyclicGraph() {
		super();
		initialize();
	}

	/**
	 * <p>
	 * Adds the given edge and updates the internal topological order for
	 * consistency IFF
	 * 
	 * <UL>
	 * <li>the given edge is not already a member of the graph
	 * <li>there is not already an edge (fromVertex, toVertex) in the graph
	 * <li>the edge does not induce a cycle in the graph
	 * </ul>
	 * </p>
	 * 
	 * @return true if the edge was added to the graph
	 * 
	 * 
	 * @see Graph#addEdge(Object, Object, Object)
	 */
	@Override
	public boolean addEdge(@Nonnull E edge, Pair<? extends V> endpoints,
			EdgeType edgeType) {

		V fromVertex = endpoints.getFirst();
		V toVertex = endpoints.getSecond();

		if (edge == null) {
			throw new IllegalStateException("Edge can't be null!");
		} else if (containsEdge(edge)) {
			return false;
		}

		if (!vertices.containsKey(fromVertex)) {
			this.addVertex(fromVertex);
		}

		if (!vertices.containsKey(toVertex)) {
			this.addVertex(toVertex);
		}

		Integer lb = this.topoOrderMap.getTopologicalIndex(toVertex);
		Integer ub = this.topoOrderMap.getTopologicalIndex(fromVertex);

		if ((lb == null) || (ub == null)) {
			throw new IllegalArgumentException(
					"vertices must be in the graph already!");
		}

		if (lb < ub) {
			Set<V> df = new HashSet<V>();
			Set<V> db = new HashSet<V>();

			// Discovery
			Region affectedRegion = new Region(lb, ub);
			Visited visited = this.visitedFactory.getInstance(affectedRegion);

			// throws CycleFoundException if there is a cycle
			try {
				dfsF(toVertex, df, visited, affectedRegion);
			} catch (CycleFoundException e1) {
				return false;
			}

			dfsB(fromVertex, db, visited, affectedRegion);
			reorder(df, db, visited);
			++this.topologyUpdateCount; // if we do a reorder, than the topology
			// has
			// been updated
		}

		return super.addEdge(edge, endpoints, edgeType);
	}

	/**
	 * adds the vertex if it wasn't already in the graph, and puts it at the top
	 * of the internal topological vertex ordering
	 */
	@Override
	public boolean addVertex(V v) {
		boolean added = super.addVertex(v);
		if (added) {
			// add to the top
			++this.maxTopoIndex;
			this.topoOrderMap.putVertex(this.maxTopoIndex, v);

			++this.topologyUpdateCount;
		}
		return added;
	}

	/**
	 * Depth first search backward, building up the set (db) of back-connected
	 * vertices in the Affected Region
	 * 
	 * @param vertex
	 *            the vertex being visited
	 * @param db
	 *            the set we are populating with back-connected vertices in the
	 *            AR
	 * @param visited
	 * @param topoIndexMap
	 */
	private void dfsB(V vertex, Set<V> db, Visited visited,
			Region affectedRegion) {
		// Assumption: vertex is in the AR and so we will get a topoIndex from
		// the map
		int topoIndex = this.topoOrderMap.getTopologicalIndex(vertex);
		visited.setVisited(topoIndex);

		db.add(vertex);

		for (E inEdge : getInEdges(vertex)) {
			V previousVertex = getSource(inEdge);
			Integer previousVertexTopoIndex = this.topoOrderMap
					.getTopologicalIndex(previousVertex);

			// note, order of checks is important as we need to make sure the
			// vertex is in the affected region before we check its visited
			// status (otherwise we will be causing an
			// ArrayIndexOutOfBoundsException).
			if (affectedRegion.isIn(previousVertexTopoIndex)
					&& !visited.getVisited(previousVertexTopoIndex)) {
				// if prevousVertexTopoIndex != null, the vertex is in the
				// Affected Region according to our topoIndexMap

				dfsB(previousVertex, db, visited, affectedRegion);
			}
		}
	}

	/**
	 * Depth first search forward, building up the set (df) of forward-connected
	 * vertices in the Affected Region
	 * 
	 * @param vertex
	 *            the vertex being visited
	 * @param df
	 *            the set we are populating with forward connected vertices in
	 *            the Affected Region
	 * @param visited
	 *            a simple data structure that lets us know if we already
	 *            visited a node with a given topo index
	 * @param topoIndexMap
	 *            for quick lookups, a map from vertex to topo index in the AR
	 * @param ub
	 *            the topo index of the original fromVertex -- used for cycle
	 *            detection
	 * 
	 * @throws CycleFoundException
	 *             if a cycle is discovered
	 */
	private void dfsF(V vertex, Set<V> df, Visited visited,
			Region affectedRegion) throws CycleFoundException {
		int topoIndex = this.topoOrderMap.getTopologicalIndex(vertex);

		// Assumption: vertex is in the AR and so it will be in visited
		visited.setVisited(topoIndex);

		df.add(vertex);

		for (E outEdge : super.getOutEdges(vertex)) {
			V nextVertex = super.getDest(outEdge);
			Integer nextVertexTopoIndex = this.topoOrderMap
					.getTopologicalIndex(nextVertex);

			if (nextVertexTopoIndex.intValue() == affectedRegion.finish) {
				// reset visited
				try {
					for (V visitedVertex : df) {
						visited.clearVisited(this.topoOrderMap
								.getTopologicalIndex(visitedVertex));
					}
				} catch (UnsupportedOperationException e) {
					// okay, fine, some implementations (ones that automatically
					// clear themselves out) don't work this way
				}
				throw new CycleFoundException();
			}

			// note, order of checks is important as we need to make sure the
			// vertex is in the affected region before we check its visited
			// status (otherwise we will be causing an
			// ArrayIndexOutOfBoundsException).
			if (affectedRegion.isIn(nextVertexTopoIndex)
					&& !visited.getVisited(nextVertexTopoIndex)) {
				dfsF(nextVertex, df, visited, affectedRegion); // recurse
			}
		}
	}

	/**
	 * set the topoOrderMap based on the current factory, and create the
	 * comparator;
	 */
	private void initialize() {
		this.topoOrderMap = this.topoOrderFactory.getTopoOrderMapping();
		this.topoComparator = new TopoComparator<V>(this.topoOrderMap);
	}

	/**
	 * iterator will traverse the vertices in topological order, meaning that
	 * for a directed graph G = (V,E), if there exists a path from vertex va to
	 * vertex vb then va is guaranteed to come before vertex vb in the iteration
	 * order.
	 * 
	 * @return an iterator that will traverse the graph in topological order
	 */
	public Iterator<V> iterator() {
		return new TopoIterator();
	}

	// note that this can leave holes in the topological ordering, which
	// (depending on the TopoOrderMap implementation) can degrade performance
	// for certain operations over time
	/**
	 * {@inheritDoc}
	 */
	@Override
	public boolean removeVertex(V v) {
		boolean removed = super.removeVertex(v);

		if (removed) {
			Integer topoIndex = this.topoOrderMap.removeVertex(v);

			// contract minTopoIndex as we are able
			if (topoIndex == this.minTopoIndex) {
				while ((this.minTopoIndex < 0)
						&& (null == this.topoOrderMap
								.getVertex(this.minTopoIndex))) {
					++this.minTopoIndex;
				}
			}

			// contract maxTopoIndex as we are able
			if (topoIndex == this.maxTopoIndex) {
				while ((this.maxTopoIndex > 0)
						&& (null == this.topoOrderMap
								.getVertex(this.maxTopoIndex))) {
					--this.maxTopoIndex;
				}
			}

			++this.topologyUpdateCount;
		}

		return removed;
	}

	@SuppressWarnings("unchecked")
	private void reorder(Set<V> df, Set<V> db, Visited visited) {
		List<V> topoDf = new ArrayList<V>(df);
		List<V> topoDb = new ArrayList<V>(db);

		Collections.sort(topoDf, this.topoComparator);
		Collections.sort(topoDb, this.topoComparator);

		// merge these suckers together in topo order

		SortedSet<Integer> availableTopoIndices = new TreeSet<Integer>();

		// we have to cast to the generic type, can't do "new V[size]" in java
		// 5;
		V[] bigL = (V[]) new Object[df.size() + db.size()];
		int lIndex = 0; // this index is used for the sole purpose of pushing
		// into

		// the correct index of bigL

		// assume (for now) that we are resetting visited
		boolean clearVisited = true;

		for (V vertex : topoDb) {
			Integer topoIndex = this.topoOrderMap.getTopologicalIndex(vertex);

			// add the available indices to the set
			availableTopoIndices.add(topoIndex);

			bigL[lIndex++] = vertex;

			if (clearVisited) { // reset visited status if supported
				try {
					visited.clearVisited(topoIndex);
				} catch (UnsupportedOperationException e) {
					clearVisited = false;
				}
			}
		}

		for (V vertex : topoDf) {
			Integer topoIndex = this.topoOrderMap.getTopologicalIndex(vertex);

			// add the available indices to the set
			availableTopoIndices.add(topoIndex);
			bigL[lIndex++] = vertex;

			if (clearVisited) { // reset visited status if supported
				try {
					visited.clearVisited(topoIndex);
				} catch (UnsupportedOperationException e) {
					clearVisited = false;
				}
			}
		}

		lIndex = 0; // reusing lIndex
		for (Integer topoIndex : availableTopoIndices) {
			// assign the indexes to the elements of bigL in order
			V vertex = bigL[lIndex++]; // note the post-increment
			this.topoOrderMap.putVertex(topoIndex, vertex);
		}
	}
}

// End DirectedAcyclicGraph.java
